package com.nine.algorithm.leetcode.list;

/**
 * @author nine
 * @version 1.0
 * @description 删除重复元素，一个不留
 * @date 24/5/5 10:39
 */
public class Leetcode082 {

	public static void main(String[] args) {
		// ListNode head = ListNode.of(1, 1, 1, 2, 3);
		ListNode head = ListNode.of(1, 2, 3, 3, 4, 4, 5);
		// 初始
		System.out.println(head);
		// head = deleteDuplicatesRecursion(head);
		head = deleteDuplicates(head);
		System.out.println(head);
	}

	/**
	 * 方法一：递归实现
	 *
	 * @param p
	 * @return
	 */
	private static ListNode deleteDuplicatesRecursion(ListNode p) {
		// 节点<2
		if (p == null || p.next == null) {
			return p;
		}
		// 值相等，需要继续往下遍历，一直找到和当前节点值不等的节点
		if (p.val == p.next.val) {
			// 定义一个指针，指向p.next.next
			ListNode x = p.next.next;
			// 当下下一个节点的值和当前节点值相等时，继续往下遍历
			while (x != null && p.val == x.val) {
				x = x.next;
			}
			// 传递与p值不相同的节点
			return deleteDuplicatesRecursion(x);
		}
		else {
			p.next = deleteDuplicatesRecursion(p.next);
			return p;
		}
	}

	/*
	  p1 p2 p3
	  s, 1, 1, 1, 2, 3, null

	  p1 p2    p3
	  s, 1, 1, 1, 2, 3, null

	  p1 p2       p3
	  s, 1, 1, 1, 2, 3, null

	  p1 p3
	  s, 2, 3, null

	  p1 p2 p3
	  s, 2, 3, null

	     p1 p2 p3
	  s, 2, 3, null
	 */
	public static ListNode deleteDuplicates(ListNode p) {
		// 节点<2
		if (p == null || p.next == null) {
			return p;
		}
		// 使用哨兵
		ListNode s = new ListNode(-1, p);
		ListNode p1 = s;
		ListNode p2, p3;

		while ((p2 = p1.next) != null && (p3 = p2.next) != null) {
			if (p2.val == p3.val) {
				// 循环方法一
				while (p2.val == p3.val) {
					p3 = p3.next;
				}
				// 循环方法二
				// while ((p3 = p3.next) != null && p2.val == p3.val) {
				// 	// 不做处理，循环结束的话，证明当前的p3和p2值不一样
				// }
				p1.next = p3;
			}
			else {
				// 将p1往后移，进入循环的话，p2和p3会依次赋值
				p1 = p1.next;
			}
		}
		return s.next;
	}

}
